package ch04;

//判断无向图是否是无环图
public class Cycle {
    private boolean[] marked;
    private boolean cycle = false;
    public Cycle(Graph graph) {

        this.marked = new boolean[graph.V()];
        for (int i = 0; i < marked.length; i++) {
            if (!marked[i]) {
                DFS(graph, i,i);
            }
        }
    }

    //DFS过程中已经访问过的点已经形成了一条链路，
    // 如果出现了已经访问的点（除了当前节点的前驱结点）则说明形成了环
    public void DFS(Graph graph, int cur,int prev) {

        marked[cur] = true;
        for (Integer w : graph.adj(cur)) {
            if(!marked[w])
                DFS(graph, w, cur);
            else{
                if(w != prev) {
                    cycle = true;
                }

            }

        }
    }
    public boolean isCycle(){
        return cycle;
    }

    public static void main(String[] args) {
        Cycle cycle = new Cycle(Graph.getGraphUseCase());
        System.out.println(cycle.isCycle());
    }
}
